use std::collections::VecDeque;
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    let rows = maze.len();
    let cols = maze[0].len();
    let directions = [(-1, 0), (1, 0), (0, -1), (0, 1)];
    let mut visited = vec![vec![false; cols]; rows];
    visited[start.0][start.1] = true;
    let mut queue = VecDeque::new();
    queue.push_back((start, vec![start]));
    while let Some((current, path)) = queue.pop_front() {
        if current == end {
            return path;
        }
        for &(dx, dy) in &directions {
            let new_x = current.0 as isize + dx;
            let new_y = current.1 as isize + dy;
            if new_x >= 0 && new_x < rows as isize && new_y >= 0 && new_y < cols as isize {
                let new_pos = (new_x as usize, new_y as usize);
                if maze[new_pos.0][new_pos.1] != '#' && !visited[new_pos.0][new_pos.1] {
                    visited[new_pos.0][new_pos.1] = true;
                    let mut new_path = path.clone();
                    new_path.push(new_pos);
                    queue.push_back((new_pos, new_path));
                }
            }
        }
    }
    vec![]
}
